# Author    :Dun_Hz
# Time      :2024/7/28 11:45
# 归并排序，创建临时新列表，有空间消耗
import random


def merge(li,low,mid,high):
    i=low
    j=mid+1
    ltmp=[]
    while i<=mid and j<=high:
        if li[i]>li[j]:
            ltmp.append(li[j])
            j+=1
        else:
            ltmp.append(li[i])
            i+=1
    while i<=mid:
        ltmp.append(li[i])
        i+=1
    while j<=high:
        ltmp.append(li[j])
        j+=1
    li[low:high+1]=ltmp     # 必须这样来修改列表值


def merge_sort(li,low,high):
    if low<high:
        mid = (low+high)//2
        merge_sort(li,low,mid)
        merge_sort(li,mid+1,high)
        merge(li,low,mid,high)

if __name__=="__main__":
    li=[i for i in range(15)]
    random.shuffle(li)
    print(li)
    merge_sort(li,0,len(li)-1)
    print(li)